package algorithm.leetcode;

import java.util.*;

public class LeetCode_488_findMinStep {
    //todo
    //bfs + 剪枝
    public static int findMinStep(String board, String hand) {
        int total = hand.length();
        Queue<String[]> queue = new LinkedList<>();
        queue.add(new String[]{board, hand});
        Set<String> cache1 = new HashSet<>();
        while (!queue.isEmpty()) {
            String[] poll = queue.poll();
            String currBoardString = poll[0];
            String currHandString = poll[1];
            char[] currBoardChars = currBoardString.toCharArray();
            char[] currHandChars = currHandString.toCharArray();

            for (int i = 0; i <= currBoardChars.length; i++) {
                Set<Character> cache2 = new HashSet<>();
                for (int j = 0; j < currHandChars.length; j++) {
                    char ball = currHandChars[j];
                    if (cache2.contains(ball)) continue;
                    cache2.add(ball);
                    String nextHandString = removeCharAt(currHandString, j);
                    String nextBoardString = currBoardString.substring(0, i) + ball + currBoardString.substring(i);

                    if (cache1.contains(nextBoardString + "-" + nextHandString)) continue;
                    cache1.add(nextBoardString + "-" + nextHandString);

                    nextBoardString = clearBoard(nextBoardString);
                    if (nextBoardString.isEmpty()) {
                        return total - nextHandString.length();
                    }

                    queue.add(new String[]{nextBoardString, nextHandString});
                }
            }
        }
        return -1;
    }

    private static String removeCharAt(String str, int idx) {
        return str.substring(0, idx) + str.substring(idx + 1);
    }

    public static String clearBoard(String board) {
        while (true) {
            boolean flag = true;
            List<Character> buff = new LinkedList<>();
            char preChar = '\0';
            for (int i = 0; i < board.length(); i++) {
                char currChar = board.toCharArray()[i];
                if (currChar != preChar) {
                    preChar = currChar;
                    if (buff.size() >= 3) {
                        board = board.substring(0, i - buff.size()) + board.substring(i);
                        flag = false;
                        buff.clear();
                        break;
                    }
                    buff.clear();
                }
                buff.add(currChar);
            }
            if (buff.size() >= 3) {
                board = board.substring(0, board.length() - buff.size());
            }
            if (flag) break;
        }
        return board;
    }

    public static void main(String[] args) {
        System.out.println(findMinStep("RRYGGYYRRYYGGYRR", "GGBBB"));
        //System.out.println(findMinStep.clearBoard("GRRYGGGYYRRYYGGYRR"));
    }
}
